#include "main/utils.h"
using namespace std;

int longestCommonSubstr1(const string& s1, const string& s2) {
  int len1 = s1.size();
  int len2 = s2.size();
  vector<vector<int>> dp;
  dp.resize(len1 + 1);
  for (int i = 0; i < len1 + 1; ++i) {
    dp[i].resize(len2 + 1, 0);
  }

  for (int i = 0; i < len1; ++i) {
    for (int j = 0; j < len2; ++j) {
      if (s1[i] == s2[j]) {
        dp[i + 1][j + 1] = dp[i][j] + 1;
      } else {
        dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
      }
    }
  }

  return dp[len1][len2];
}

int longestCommonSubstr2(const string& s1, const string& s2) {
  int len1 = s1.size();
  int len2 = s2.size();
  if (len1 < len2)
    return longestCommonSubstr2(s2, s1);

  vector<vector<int>> dp;
  dp.resize(2);
  for (int i = 0; i < 2; ++i) {
    dp[i].resize(len2 + 1, 0);
  }

  for (int i = 0; i < len1; ++i) {
    for (int j = 0; j < len2; ++j) {
      if (s1[i] == s2[j]) {
        dp[(i + 1) % 2][j + 1] = dp[i % 2][j] + 1;
      } else {
        dp[(i + 1) % 2][j + 1] = max(dp[i % 2][j + 1], dp[(i + 1) % 2][j]);
      }
    }
  }

  return dp[len1 % 2][len2];
}

int longestCommonSubstr3(const string& s1, const string& s2) {
  int len1 = s1.size();
  int len2 = s2.size();
  if (len1 < len2)
    return longestCommonSubstr3(s2, s1);

  vector<int> dp(len2 + 1, 0);
  for (int i = 0; i < len1; ++i) {
    int tmp = dp[0];
    for (int j = 0; j < len2; ++j) {
      int cur;
      if (s1[i] == s2[j]) {
        cur = tmp + 1;
      } else {
        cur = max(dp[j + 1], dp[j]);
      }
      tmp = dp[j + 1];
      dp[j + 1] = cur;
    }
  }

  return dp[len2];
}

int main() {
  string s1 = "abcde";
  string s2 = "badfe";
  cout << longestCommonSubstr1(s1, s2) << endl;
  cout << longestCommonSubstr2(s1, s2) << endl;
  cout << longestCommonSubstr3(s1, s2) << endl;

  return 0;
}
